class TreeNode {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

const root1 = new TreeNode("A");
root1.left = new TreeNode("B");
root1.right = new TreeNode("C");
root1.left.left = new TreeNode("D");
root1.left.right = new TreeNode("E");
root1.right.left = new TreeNode("F");

/* Tree 1 结构：
 *        A
 *      /   \
 *     B     C
 *    / \   /
 *   D   E F
 */


const root2 = new TreeNode("A");
root2.left = new TreeNode("B");
root2.right = new TreeNode("C");
root2.left.left = new TreeNode("D");
// 修改：将 E 替换为 G（值不同）
root2.left.right = new TreeNode("G");
// 修改：删除了 C 的左子节点 F
// 新增：在 C 的右边新增一个 H
root2.right.right = new TreeNode("H");

/* Tree 2 结构（与 Tree 1 有差异）：
 *        A
 *      /   \
 *     B     C
 *    / \     \
 *   D   G     H
 *  （E→G，F删，H增）
 */
function handleDiff(type,originNode,nowNode,parent1,parent2,diffList){
    const parentValue1=parent1?.value
    const parentValue2=parent2?.value
    if(parentValue2!==parentValue1){
        //1.父节点也变化了，需要记录
        diffList.push({
            type,
            origin:originNode,
            nowNode:nowNode,
            oldParent:parent1,
            newParent:parent2
        })
    }else{
        //2.父节点未变化，只记录一个就行
        diffList.push({
            type,
            origin:originNode,
            nowNode:nowNode,
            parent:parent1 //都一样
        })
    }
}
function diffTree(node1, node2, diffList, parent1 = null, parent2 = null) {
    // 1. 如果两个节点完全相同（包括引用地址相同或都为 null），说明没有差异，直接跳过
    if (node1 === node2 || (node1 === null && node2 === null)) return diffList;

    // 2. 旧树无此节点，但新树有，说明是“新增”操作
    if (node1 === null && node2 !== null) {
        handleDiff("新增", null, node2, parent1, parent2, diffList);
        // 已经处理完该新增节点（及其上下文），无需继续递归（因为旧树中没有这个节点）
        return diffList;
    }

    // 3. 新树无此节点，但旧树有，说明是“删除”操作
    if (node1 !== null && node2 === null) {
        handleDiff("删除", node1, null, parent1, parent2, diffList);
        // 已经记录了该节点的删除，无需继续递归（因为新树中没有它的任何后代）
        return diffList;
    }

    // 4. 节点值发生变化，说明是“修改”操作
    if (node1.value !== node2.value) {
        handleDiff("修改", node1, node2, parent1, parent2, diffList);
        // 注意：修改之后仍然要递归比较它们的子节点
    }

    // 5. 递归比较左子树
    diffTree(node1.left, node2.left, diffList, node1, node2);

    // 6. 递归比较右子树
    diffTree(node1.right, node2.right, diffList, node1, node2);

    // 7. 所有比较完成后返回差异列表（供最外层使用）
    return diffList;
}

let diffList=[]
const differences = diffTree(root1, root2,diffList);
console.log(JSON.stringify(differences, null, 2));

